package array.slidingWindow;

import java.util.HashMap;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * <p>
 * 注意：
 * <p>
 * - 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * - 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 */
public class N76_MinWindowsSubstring {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> mapT = new HashMap<>();
        HashMap<Character, Integer> mapS = new HashMap<>();

        // 统计字符串t的每个字符数
        for (char c : t.toCharArray()) {
            mapT.put(c, mapT.getOrDefault(c, 0) + 1);
        }

        int left = 0, len = Integer.MAX_VALUE,
                // 最后得到的字串在字符串中的索引，关系是[resLeft, resRight) 对应String.subString也是这样的切取字串的
                resLeft = -1, resRight = -1;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 如果该字符在t中没有，直接跳过本次循环，下一位。
            if (!mapT.containsKey(c))
                continue;
            // 没有被跳过那就是t中有，直接加入mapS，统计个数
            mapS.put(c, mapS.getOrDefault(c, 0) + 1);

            // 当字串合法，开始缩小左边界
            while (isSubStr(mapS, mapT) && left <= right) {
                // 如果字串这个合法字串比之前的最短字串更段，则更新索引
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    resLeft = left;
                    resRight = left + len;
                }
                // 缩小左边界，先把左边界那一位从mapS中移除
                if (mapS.containsKey(s.charAt(left))) {
                    mapS.put(s.charAt(left), mapS.get(s.charAt(left)) - 1);
                }
                // 左边界缩小
                left++;
            }
        }
        // 最优边界没有被修改过，则说明没有任何合法字串，返回空字符串
        return resLeft == -1 ? "" : s.substring(resLeft, resRight);
    }

    // 判断字串是否合法，比较两个HashMap，如果T中有的S都有并且S中的个数都大于等于T中的，即合法字串
    private boolean isSubStr(HashMap<Character, Integer> mapS, HashMap<Character, Integer> mapT) {
        for (Character c : mapT.keySet()) {

            if (mapS.getOrDefault(c, 0) < mapT.get(c))
                return false;
        }
        return true;
    }


    public static void main(String[] args) {
        N76_MinWindowsSubstring solution = new N76_MinWindowsSubstring();
        String s = "YUYUDEQIU", t = "YDQ";
        System.out.println(solution.minWindow(s, t));
    }
}
